﻿/*
题目: 旋转矩阵

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

https://leetcode.cn/problems/rotate-matrix-lcci/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    /**
    * 先水平翻转，再对角线翻转
    */
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();

        // 水平 (x 轴) 翻转
        for (int i = 0; i < (n >> 1); i++) {
            for (int j = 0; j < m; j++) {
                ::swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }

        // 按 左上->右下 对角线对称，并且对角线本身不用变
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                ::swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};
